package com.algrithom.dfs;

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

/**
 * 78. 子集
 * 90. 子集 II
 */
public class Solution2 {
    
    List<List<Integer>> ans = new LinkedList<>();
    
    LinkedList<Integer> path = new LinkedList<>();
    
    public static void main(String[] args){
        int[] array = new int[]{1,1,2,2};
        Solution2 solution2 = new Solution2();
        List<List<Integer>> result = solution2.subsetsWithDup3(array);
    }
    
    public List<List<Integer>> subsets(int[] nums){
        List<List<Integer>> result = new LinkedList<>();
        dfs(nums,0,new LinkedList<>(),result);
        return result;
    }
    
    public List<List<Integer>> subsetsWithDup(int[] nums){
        List<List<Integer>> result = new LinkedList<>();
        dfs2(nums,0,new HashSet<>(),new LinkedList<>(),result);
        return result;
    }
    
    private void dfs(int[] nums,int index,List<Integer> array,List<List<Integer>> result){
        result.add(new LinkedList<>(array));
        for (int i = index; i < nums.length; i++) {
            if (array.contains(nums[i])) {
                continue;
            }
            array.add(nums[i]);
            dfs(nums,i + 1,array,result);
            array.remove(array.size() - 1);
        }
    }
    
    private void dfs2(int[] nums,int index,Set<Integer> set,List<Integer> array,List<List<Integer>> result){
        boolean status = result.stream().anyMatch(val -> Arrays.equals(val.stream().sorted().mapToInt(Integer::intValue).toArray(),array.stream().sorted().mapToInt(Integer::intValue).toArray()));
        if (!status) {
            result.add(new LinkedList<>(array));
        }
        for (int i = index; i < nums.length; i++) {
            if (set.contains(i)) {
                continue;
            }
            set.add(i);
            array.add(nums[i]);
            dfs2(nums,i + 1,set,array,result);
            set.remove(i);
            array.remove(array.size() - 1);
        }
    }
    
    public List<List<Integer>> subsetsWithDup3(int[] nums){
        int len = nums.length;
        Arrays.sort(nums);
        backtrack(0,nums,len);
        return ans;
    }
    
    private void backtrack(int startIndex,int[] nums,int len){
        ans.add(new LinkedList<>(path));
        if (startIndex == len) {
            return;
        }
        
        for (int i = startIndex; i < len; i++) {
            path.add(nums[i]);
            backtrack(i + 1,nums,len);
            path.removeLast();
//            while (i + 1 < len && nums[i] == nums[i + 1]) {
//                i++;
//            }
        }
    }
}
